This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
There are many different cryptographic schemes. Leila El Aimani describes a few in “Design and Analysis of Opaque Signatures”, Dissertation Rheinischen Friedrich-Wilhelms-Universität Bonn (http://hss.ulb.uni-bonn.de/2011/2541/2541.pdf), notably confirmer and undeniable signatures, i.e. signatures where the verification cannot be achieved without cooperation with some entity. In this thesis, the author essentially studies how to build such signatures from basic cryptographic primitives. She shows that the traditional paradigms (e.g. Encrypt_then_Sign and Commit_then_Encrypt_and_Sign) need expensive encryption in order to meet a reasonable security level. Next, she shows that small adjustments make the constructions thrive on cheap encryption, which positively impacts the efficiency (e.g. cost, bandwidth, verifiability) of the resulting signatures. However, the signatures do not offer encryption of the message to be signed.
Cryptographic mechanisms that proffer both signature and encryption functionalities, so-called signcryption, are becoming more and more widespread as many real-life applications require both confidentiality and authenticity/integrity of the transmitted data. An illustrative example is electronic elections in which encryption is needed to guarantee the voter's privacy, while at the same time the voting center needs to ensure that the encrypted vote comes from the voter.
Building such mechanisms from basic cryptographic primitives is customary in cryptography as it allows achieving easy-to-analyze schemes, compared to dedicated, monolithic constructions. The most popular prior art paradigms used to devise these mechanisms from basic cryptographic primitives are the “encrypt_then_sign” (EtS) and the “sign_then_encrypt” (StE) paradigms.
Encrypt_then_sign (EtS)
The sender has a public key/secret key pair (Spk, Ssk) and the receiver has a different public key/secret key pair (Epk, Esk).
The sender encrypts a plaintext m using the receiver's public key Epk to obtain ciphertext e. Then the ciphertext e is signed using the sender's secret key Ssk to obtain a signature s. The pair (e, s) forms the signcryption of plaintext m.
The sender can at that time also prove knowledge of the message underlying the encryption e. The skilled person will appreciate that this can be efficiently performed if the used encryption scheme belongs to the “class E” (see Leila El Aimani: Efficient Confirmer Signatures from the “Signature of a Commitment” Paradigm. ProvSec 2010: 87-101. The paper also describes the required protocol along with its security proof for confirmer signatures from the Commit_then_Encrypt_and_Sign paradigm. It is shown that the paradigm must rest on expensive encryption in order to lead to secure confirmer signatures. However, a small tweak makes it thrive on very cheap encryption leading consequently to constructions with many practical realizations. The paper further sheds light on a particular case of this technique, namely Encrypt_then_Sign, and presents several practical realizations of confirmer signatures using this solution. However, the primitive subject to this study does not allow encryption of the message to be signed.) Class E consists of homomorphic encryption schemes that accept efficient protocols for proving that a given ciphertext encrypts a given message. Examples of such encryption schemes are ElGamal's encryption [Taher El Gamal: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. CRYPTO 1984:10-18], Paillier's encryption [Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. EUROCRYPT 1999: 223-238] and the Linear Diffie-Hellman KEM/DEM [Dan Boneh, Xavier Boyen, Hovav Shacham: Short Group Signatures. CRYPTO 2004: 41-55].
The receiver uses the sender's public key Spk to check that the signature s of the ciphertext e is correct. Then, if the signature is correct, the receiver decrypts the ciphertext e using the receiver's secret key Esk to obtain plaintext message m.
The receiver may at any time prove to anyone that m is (or isn't) the decryption of e, preferably without disclosing the private key. In EtS such proofs, called “confirm/deny protocols”, amount to proving that a ciphertext is (or isn't) the decryption of a given message. These proofs make sense when it is difficult to check whether a given ciphertext encrypts a given message, i.e. when the used encryption scheme satisfies the indistinguishability property which posits the difficulty to distinguish ciphertexts based on the underlying messages. Typically, given two messages and an encryption of one of them, one should not be able to tell which message corresponds to the given ciphertext. Since the security of the Signcryption constructions requires the indistinguishability property of the underlying encryption, encryption schemes that allow the aforementioned proofs to be efficiently carried out must be considered. Again, encryption schemes from the class E achieve this goal as shown in [Laila El Aimani: Efficient Confirmer Signatures from the “Signature of a Commitment” Paradigm. ProvSec 2010: 87-101].
Sign_then_encrypt (StE)
As in EtS, the sender has a public key/secret key pair (Spk, Ssk) and the receiver has a different public key/secret key pair (Epk, Esk).
StE can be implemented in a simple manner using a prior art signature method and a prior art signature encryption method.
US 2005/240762 describes another solution for signcrypting a message using the Sign_then_Encrypt paradigm. The idea consists in first producing a signature, using RSA, on the message to be signed, and then encrypting, using again the RSA yet with a different key pair, the produced signature. The result forms the signcryption of the message in question. De-signcrypting (decrypting and verifying) this signcryption is done by first decrypting it, verifying the output signature on the encoding, and finally recovering the message underlying the encoding. The solution does not appear to provide the verifiability functionality, i.e. efficiently proving the well formedness of the produced signcryption without the presence of the message. Indeed, efficient verifiability of the solution does not seem plausible due to the presence of hash functions and XOR operators that destroy any algebraic property susceptible of easing the verifiability.
Another way to implement StE is to build a signcryption scheme from a digital signature scheme and an encryption scheme; it is a combination of two mechanisms: A Key Encapsulation Mechanism (KEM) which is a mechanism for session keys generation, and a Data Encapsulation Mechanism (DEM) which is a symmetric key encryption scheme.
KEM consists of a triplet of algorithms (Key generation, Encapsulation, Decapsulation). Key generation generates a key pair (pk,sk). Encapsulation generates a key k and its encapsulation c using pk, and Decapsulation retrieves the key from its encapsulation using the private key sk. An example is the KEM underlying the ElGamal encryption scheme.
DEM—Data Encapsulation Mechanisms—encrypt data, usually using a symmetric key encryption algorithm.
StE is illustrated in FIG. 1. A random number r, KEM's encapsulation algorithm and a public key pk are used to obtain a session key k and its encapsulation c. The sender then uses its secret key Ssk to sign a concatenation of the plaintext m and the encapsulation c, thus obtaining signature s. (not illustrated). The DEM encryption algorithm and the session key k are used to encrypt (m,s) and obtain e. The pair (c,e) forms the signcryption of m. To “unsigncrypt” (c,e), the session key k is recovered from its encapsulation c using KEM's decapsulation algorithm and the private key. Then DEM's decryption algorithm and the session key k are used to decrypt e to obtain (m,s). Finally, the validity of the signature s may be verified using the sender's public key.
The sender further needs to prove the validity of the obtained signcryption. In StE, this proof comes to proving the knowledge of the decryption of e, and that this decryption is the concatenation of the message to be signcrypted and of a signature on this very message concatenated with c.
The proof is plausible from a theoretical viewpoint [Oded Goldreich, Silvio Micali, Avi Wigderson: How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design. CRYPTO 1986: 171-185]. However, it is not known how to do it efficiently as the data to be proven consists of bit-strings and not of algebraic elements.
An example of a KEM/DEM encryption scheme is ELGamal's encryption:                1. ElGamal.Setup. We work in a group G denoted multiplicatively, generated by some g. The group G is finite and has order some d.        2. ElGamal.Keygen. The key generation algorithm inputs a security parameter and outputs an integer x in Zd, and the group element y=gx. The key pair is (sk=x,pk=y).        3. ElGamal.Encrypt (m). [First step: KEM encapsulation algorithm]: generate a key k=yr and its encapsulation c=gr using some random r in Zd. [Second step: DEM encryption algorithm]: encrypt m in e=m·k. [Final output]: (c,e) forms the encryption of m.        4. ElGamal.Decrypt (c,e). [First step: KEM decapsulation algorithm]: using x, recover from c the key k as k=cx=(gr)x=(gx)r=yr [Second step: DEM decryption algorithm]: recover m as m=c·k−1.        
Finally, in order to be able to prove the validity of the constructions efficiently it is required that the used encryption schemes (derived from the KEM/DEM paradigm) belong to the previously mentioned “class E”, i.e. that the encryption is homomorphic and accepts efficient proofs for proving that a given ciphertext encrypts a given message. This is the case for El Gamal's encryption.
In general, the following properties are required for verifiable signcryption:                1. Unforgeability: it is computationally infeasible to impersonate the sender for some message (not necessarily controlled by the adversary).        2. Indistinguishability: it should be computationally infeasible to infer any information about the message from its signcryption.        3. Verifiability: the possibility to prove efficiently the validity of a signcryption.        
Considering once more the example of electronic elections, the voting center might require from the voter a proof of validity of the “signcrypted” vote. Also, the trusted party (the receiver) that decrypts the vote might be compelled, for instance in order to resolve later disputes, to prove that the sender has indeed produced the vote in question. Therefore, it would be desirable to support the receiver with efficient means to provide such a proof without having to disclose his private key.
In light of these properties, EtS and StE perform as follows:
EtS compares better with respect to verifiability, since the sender simply has needs to prove knowledge of the decryption of a given ciphertext. Also, the receiver has to prove that a message is or is not the decryption of a given ciphertext. Such proofs are easy to carry out if one considers a special class of encryption called homomorphic encryption. However, in order to achieve indistinguishability, EtS exacts that the underlying signature scheme satisfies the highest security notion, i.e. strong unforgeability under chosen message attacks which informally denotes the difficulty to obtain a new signature on a message for which the adversary might have obtained one or several signatures. Such a need is justified by the possibility, in case the signature scheme does not satisfy the aforementioned requirement, to create a new signcryption on any message given one signcryption on it (just generate a new digital signature on the encryption e). Such a possibility entitles the indistinguishability adversary to retrieve the message in most popular attack models.
StE does not require high security notions on the underlying signature scheme since in this case the adversary does not have in clear the involved digital signature. Another argument in favour of StE is that it provides full anonymity of the sender; the signcryption on a message m is a ciphertext, whereas in EtS, everyone can check whether the sender was involved in a signcryption (e,s) by simply checking the validity of the digital signature (using the sender's public key) on the ciphertext e. However, verifiability turns out to be a hurdle: the technique applies the signing algorithm (of the used signature scheme) to the message to be signcrypted concatenated with the used encapsulation. It further produces an encryption of the resulting signature concatenated with the message in question. To prove the validity of the produced signcryption, it is necessary to exploit the homomorphic properties of the signature and of the encryption schemes in order to provide proofs of knowledge of the encrypted signature and message. As a consequence, the used encryption and signature schemes need to operate on elements from a set with a known algebraic structure rather than on bit-strings.
To sum-up, EtS provides efficient verifiability at the expense of the sender's anonymity and of the security requirements on the building blocks. StE achieves better privacy using cheap constituents at the expense of verifiability.
The skilled person will appreciate that there is a need for a solution that combines the advantages of EtS and StE, while avoiding their drawbacks. This invention provides such a solution.